/*
    1️⃣ 用前缀和表示任意子数组的和，将问题转化为：
    有没有两个前缀和差值为 k。
    2️⃣ 用哈希表记录前缀和出现次数，
    在遍历中查找当前前缀和减去 k 是否已出现过，从而统计满足条件的子数组个数。
    这就是它快的本质：用“前缀差值 + 哈希计数”代替暴力枚举所有区间。
*/



// #include "uthash.h"  // uthash 提供 HASH_FIND_INT、HASH_ADD_INT、HASH_DEL、HASH_ITER 等哈希表宏操作

// step 1# 定义哈希表节点结构：用于记录某前缀和出现的次数
typedef struct {
    int key;              // 前缀和的数值
    int count;            // 出现次数
    UT_hash_handle hh;    // uthash 用于构建哈希表结构
} HashItem;

// step 2# 子数组和为 k 的个数计算函数
int subarraySum(int* nums, int numsSize, int k) {
    // step 3# 计算前缀和数组 s，s[i] 表示前 i 项的和（s[0]=0）
    int* s = (int*)calloc(numsSize + 1, sizeof(int));  // calloc 自动初始化为 0
    for (int i = 0; i < numsSize; i++) {
        s[i + 1] = s[i] + nums[i];  // 构造前缀和
    }

    // step 4# 初始化哈希表 map，用于统计前缀和的出现次数
    HashItem* map = NULL;  // uthash 哈希表头指针
    int ans = 0;           // 记录答案：满足条件的子数组个数

    // step 5# 遍历前缀和数组 s
    for (int i = 0; i <= numsSize; i++) {
        int target = s[i] - k;  // step 5.1# 查找是否存在某前缀和使得当前区间和为 k

        // step 5.2# 查找哈希表中是否存在 key = target
        HashItem* found = NULL;
        HASH_FIND_INT(map, &target, found);  // 查找 target 是否存在
        if (found != NULL) {
            ans += found->count;  // 如果存在，累加其出现次数
        }

        // step 5.3# 插入或更新 key = s[i] 到哈希表中
        HashItem* item = NULL;
        HASH_FIND_INT(map, &s[i], item);     // 查找当前前缀和是否已存在
        if (item == NULL) {
            item = (HashItem*)malloc(sizeof(HashItem)); // 新建节点
            item->key = s[i];     // 设置 key 为当前前缀和
            item->count = 1;      // 首次出现，次数设为 1
            HASH_ADD_INT(map, key, item);    // 加入哈希表
        } else {
            item->count += 1;     // 已存在则出现次数加一
        }
    }

    // step 6# 释放哈希表内存，防止内存泄漏
    HashItem *cur, *tmp;
    HASH_ITER(hh, map, cur, tmp) {  // 遍历哈希表
        HASH_DEL(map, cur);         // 删除元素
        free(cur);                  // 释放内存
    }

    // step 7# 释放前缀和数组内存并返回答案
    free(s);
    return ans;
}
